package cn.nicklemay.interview.algorithm;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Merge_k_Sorted_Lists
{

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>()
        {
            @Override
            public int compare(ListNode o1, ListNode o2)
            {
                if (o1.val > o2.val)
                {
                    return 1;
                } else if (o1.val < o2.val)
                {
                    return -1;
                } else
                {
                    return 0;
                }
            }
        });

        for (ListNode node : lists)
        {
            if (node != null)
            {
                queue.add(node);
            }
        }

        ListNode ln = new ListNode(0);
        ListNode res = ln;
        while (!queue.isEmpty())
        {
            ListNode listNode = queue.poll();
            ln.next = listNode;
            ln = ln.next;

            if (ln.next!=null)
            {
                queue.add(ln.next);
            }
        }
        return res.next;
    }

    public class ListNode
    {
        int val;
        ListNode next;

        ListNode(int x)
        {
            val = x;
        }
    }
}
